﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithms
{
    public class Node<T> where T : IComparable
    {
        private Node<T> parent;
        private Node<T> leftChild;
        private Node<T> rightChild;
        private Node<T> middleChild;

        // When node is 2-node, leftVal is the values, and rightVal is null.
        private T leftVal;
        private T rightVal;

        private bool twoNode;

        int depth = 0;

        protected Node()
        {
        }

        public static Node<T> CreateTwoNode(T value)
        {
            Node<T> node = new Node<T>();
            node.leftVal = value;
            node.twoNode = true;
            return node;
        }


        public static Node<T> CreateThreeNode(T leftVal, T rightVal)
        {
            Node<T> node = new Node<T>();
            if (leftVal.CompareTo(rightVal) > 0)
            {
                node.rightVal = leftVal;
                node.leftVal = rightVal;
            }
            else
            {
                node.leftVal = leftVal;
                node.rightVal = rightVal;
            }
            node.twoNode = false;
            return node;
        }


        public static HoleNode<T> CreateHole()
        {
            return new HoleNode<T>();
        }

        public virtual void SetLeftChild(Node<T> leftChild)
        {
            this.leftChild = leftChild;
            if (leftChild != null)
            {
                leftChild.SetParent(this);
            }
            else
            {

            }
        }

        public virtual void RemoveChildren()
        {
            this.leftChild = null;
            this.rightChild = null;
        }


        public virtual void SetRightChild(Node<T> rightChild)
        {
            this.rightChild = rightChild;
            if (rightChild != null)
            {
                rightChild.SetParent(this);
            }
            else
            {

            }
        }

        public virtual void SetMiddleChild(Node<T> middleChild)
        {
            System.Diagnostics.Debug.Assert(IsThreeNode());

            this.middleChild = middleChild;
            if (middleChild != null)
            {
                middleChild.SetParent(this);
            }
            else
            {
            }

        }

        public Node<T> Parent()
        {
            return parent;
        }

        public void SetParent(Node<T> parent)
        {
            this.parent = parent;
            if (parent == null)
            {
                SetDepth(0);
            }
            else
            {
                int d = parent.GetDepth();

                SetDepth(d + 1);

            }
        }

        public bool IsTerminal()
        {
            return leftChild == null && rightChild == null;
        }


        public T Value()
        {
            System.Diagnostics.Debug.Assert(IsTwoNode());
            return leftVal;
        }

        public void SetValue(T value)
        {
            System.Diagnostics.Debug.Assert(IsTwoNode());
            leftVal = value;
        }

        public T LeftValue()
        {
            System.Diagnostics.Debug.Assert(IsThreeNode());
            return leftVal;
        }

        public T RightValue()
        {
            System.Diagnostics.Debug.Assert(IsThreeNode());
            return rightVal;
        }

        public void SetLeftValue(T leftVal)
        {
            System.Diagnostics.Debug.Assert(IsThreeNode());
            this.leftVal = leftVal;
        }

        public void SetRightValue(T rightVal)
        {
            System.Diagnostics.Debug.Assert(IsThreeNode());
            this.rightVal = rightVal;
        }

        public virtual bool IsTwoNode()
        {
            // return rightVal == null;
            return twoNode;
        }

        public virtual bool IsThreeNode()
        {
            return !IsTwoNode();
        }

        public virtual Node<T> LeftChild()
        {
            return leftChild;
        }

        public virtual Node<T> RightChild()
        {
            return rightChild;
        }

        public virtual Node<T> MiddleChild()
        {
            System.Diagnostics.Debug.Assert(IsThreeNode());
            return middleChild;
        }

        public virtual void ReplaceChild(Node<T> currentChild, Node<T> newChild)
        {
            if (currentChild == leftChild)
            {
                leftChild = newChild;
            }
            else if (currentChild == rightChild)
            {
                rightChild = newChild;
            }
            else
            {
                System.Diagnostics.Debug.Assert(middleChild == currentChild);
                middleChild = newChild;
            }
            newChild.SetParent(this);
            currentChild.SetParent(null);
        }

        public void SetDepth(int depth)
        {
            this.depth = depth;
        }

        public int GetDepth()
        {
            return this.depth;
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            if (IsTwoNode())
            {
                sb.AppendFormat("d:{0} v:{1}", this.depth, leftVal);
                //return  leftVal.ToString();
            }
            else if (IsThreeNode())
            {
                sb.AppendFormat("d:{0} v:({1}-{2})", this.depth, leftVal, rightVal);
            }

            return sb.ToString();

        }
    }

    /**
     * A hole node does not have any values, and have only one child.
     */
    public class HoleNode<T> : Node<T> where T : IComparable
    {
        private Node<T> child;

        public HoleNode()
            : base()
        {

        }

        public override bool IsTwoNode()
        {
            return false;
        }

        public Node<T> Sibling()
        {
            if (Parent() != null)
            {
                Node<T> parent = Parent();
                return parent.LeftChild() == this ? parent.RightChild() : parent.LeftChild();
            }
            return null;
        }


        public override void RemoveChildren()
        {
            child = null;
        }

        public Node<T> Child()
        {
            return child;
        }

        public void SetChild(Node<T> child)
        {
            this.child = child;
        }
    }


    public class TwoThreeTree<T> : ICollection<T> where T : IComparable
    {
        private static readonly Exception DUPLICATE = new Exception("DuplicateException");
        private Node<T> root;
        private int size = 0;

        public void Add(T value)
        {
            if (root == null)
            {
                root = Node<T>.CreateTwoNode(value);
            }
            else
            {
                try
                {
                    Node<T> result = Insert(value, root);
                    if (result != null)
                    {
                        root = result;
                    }
                }
                catch (Exception e)
                {
                    throw e;
                }

            }
            size++;
        }

        public bool Contains(T value)
        {
            return FindNode(root, value) != null;
        }

        private Node<T> FindNode(Node<T> node, T value)
        {
            if (node == null) return null;

            if (node.IsThreeNode())
            {
                int leftComp = value.CompareTo(node.LeftValue());
                int rightComp = value.CompareTo(node.RightValue());
                if (leftComp == 0 || rightComp == 0)
                {
                    return node;
                }
                if (leftComp < 0)
                {
                    return FindNode(node.LeftChild(), value);
                }
                else if (rightComp < 0)
                {
                    return FindNode(node.MiddleChild(), value);
                }
                else
                {
                    return FindNode(node.RightChild(), value);
                }
            }
            else
            {
                int comp = value.CompareTo(node.Value());
                if (comp == 0)
                    return node;
                if (comp < 0)
                    return FindNode(node.LeftChild(), value);
                else
                    return FindNode(node.RightChild(), value);
            }
        }

        private Node<T> Insert(T value, Node<T> node)
        {
            Node<T> returnValue = null;
            if (node.IsTwoNode())
            {
                int comp = value.CompareTo(node.Value());

                if (node.IsTerminal())
                {
                    if (comp == 0)
                    {
                        throw DUPLICATE;
                    }
                    Node<T> thnode = Node<T>.CreateThreeNode(value, node.Value());
                    Node<T> parent = node.Parent();
                    if (parent != null)
                    {
                        parent.ReplaceChild(node, thnode);
                    }
                    else
                    {
                        root = thnode;
                    }
                }
                else
                {
                    if (comp < 0)
                    {
                        Node<T> result = Insert(value, node.LeftChild());
                        if (result != null)
                        {
                            Node<T> threeNode = Node<T>.CreateThreeNode(result.Value(), node.Value());
                            threeNode.SetRightChild(node.RightChild());
                            threeNode.SetMiddleChild(result.RightChild());
                            threeNode.SetLeftChild(result.LeftChild());
                            if (node.Parent() != null)
                            {
                                node.Parent().ReplaceChild(node, threeNode);
                            }
                            else
                            {
                                root = threeNode;
                            }
                            UnlinkNode(node);
                        }
                    }
                    else if (comp > 0)
                    {
                        Node<T> result = Insert(value, node.RightChild());
                        if (result != null)
                        {
                            Node<T> threeNode = Node<T>.CreateThreeNode(result.Value(), node.Value());
                            threeNode.SetLeftChild(node.LeftChild());
                            threeNode.SetMiddleChild(result.LeftChild());
                            threeNode.SetRightChild(result.RightChild());
                            Node<T> parent = node.Parent();
                            if (parent != null)
                            {
                                parent.ReplaceChild(node, threeNode);
                                int depth = threeNode.GetDepth() + 1;
                                threeNode.LeftChild().SetDepth(depth);
                                threeNode.MiddleChild().SetDepth(depth);
                                threeNode.RightChild().SetDepth(depth);
                            }
                            else
                            {
                                root = threeNode;
                            }
                            UnlinkNode(node);
                        }
                    }
                    else
                    {
                        throw DUPLICATE;
                    }
                }

            }
            else
            { // three node
                Node<T> threeNode = node;

                int leftComp = value.CompareTo(threeNode.LeftValue());
                int rightComp = value.CompareTo(threeNode.RightValue());
                if (leftComp == 0 || rightComp == 0)
                {
                    throw DUPLICATE;
                }

                if (threeNode.IsTerminal())
                {
                    returnValue = SplitNode(threeNode, value);
                }
                else
                {
                    if (leftComp < 0)
                    {
                        Node<T> result = Insert(value, threeNode.LeftChild());
                        if (result != null)
                        {
                            returnValue = SplitNode(threeNode, result.Value());
                            returnValue.LeftChild().SetLeftChild(result.LeftChild());
                            returnValue.LeftChild().SetRightChild(result.RightChild());
                            returnValue.RightChild().SetLeftChild(threeNode.MiddleChild());
                            returnValue.RightChild().SetRightChild((threeNode.RightChild()));
                            UnlinkNode(threeNode);
                        }
                    }
                    else if (rightComp < 0)
                    {
                        Node<T> result = Insert(value, threeNode.MiddleChild());
                        if (result != null)
                        {
                            returnValue = SplitNode(threeNode, result.Value());
                            returnValue.LeftChild().SetLeftChild(threeNode.LeftChild());
                            returnValue.LeftChild().SetRightChild(result.LeftChild());
                            returnValue.RightChild().SetLeftChild(result.RightChild());
                            returnValue.RightChild().SetRightChild(threeNode.RightChild());
                            UnlinkNode(threeNode);
                        }
                    }
                    else
                    {
                        Node<T> result = Insert(value, threeNode.RightChild());
                        if (result != null)
                        {
                            returnValue = SplitNode(threeNode, result.Value());
                            returnValue.LeftChild().SetLeftChild(threeNode.LeftChild());
                            returnValue.LeftChild().SetRightChild(threeNode.MiddleChild());
                            returnValue.RightChild().SetLeftChild(result.LeftChild());
                            returnValue.RightChild().SetRightChild(result.RightChild());
                            UnlinkNode(threeNode);
                        }
                    }
                }
            }
            return returnValue;
        }

        public bool Remove(T value)
        {
            if (value == null)
            {
                return false;
            }

            Node<T> node = FindNode(root, value);
            if (node == null)
            {
                return false;
            }

            HoleNode<T> hole = null;
            Node<T> terminalNode;
            T holeValue;
            if (node.IsTerminal())
            {
                terminalNode = node;
                holeValue = value;
            }
            else
            {
                // Replace by successor.
                if (node.IsThreeNode())
                {
                    if (node.LeftValue().Equals(value))
                    {
                        Node<T> pred = Predecessor(node, value);
                        holeValue = pred.IsThreeNode() ? pred.RightValue() : pred.Value();
                        node.SetLeftValue(holeValue);
                        terminalNode = pred;
                    }
                    else
                    {
                        Node<T> succ = Successor(node, value);
                        holeValue = succ.IsThreeNode() ? succ.LeftValue() : succ.Value();
                        node.SetRightValue(holeValue);
                        terminalNode = succ;
                    }
                }
                else
                {
                    Node<T> succ = Successor(node, value);
                    holeValue = succ.IsThreeNode() ? succ.LeftValue() : succ.Value();
                    node.SetValue(holeValue);
                    terminalNode = succ;
                }
            }

            System.Diagnostics.Debug.Assert(terminalNode.IsTerminal());

            if (terminalNode.IsThreeNode())
            {
                // Easy case. Replace 3-node by 2-node
                T val = terminalNode.LeftValue().Equals(holeValue) ? terminalNode.RightValue() : terminalNode.LeftValue();
                Node<T> twoNode = Node<T>.CreateTwoNode(val);
                if (terminalNode.Parent() != null)
                {
                    terminalNode.Parent().ReplaceChild(terminalNode, twoNode);
                }
                else
                {
                    root = twoNode;
                }
            }
            else
            {
                if (terminalNode.Parent() != null)
                {
                    hole = Node<T>.CreateHole();
                    terminalNode.Parent().ReplaceChild(terminalNode, hole);
                }
                else
                {
                    root = null;
                }
            }

            // For description of each case see
            // "2-3 Tree Deletion: Upward Phase" in  http://cs.wellesley.edu/~cs230/spring07/2-3-trees.pdf
            while (hole != null)
            {
                // Case 1. The hole has a 2-node as parent and 2-node as sibling.
                if (hole.Parent().IsTwoNode() && hole.Sibling().IsTwoNode())
                {
                    //System.out.println("Case 1");
                    Node<T> parent = hole.Parent();
                    Node<T> sibling = hole.Sibling();

                    Node<T> threeNode = Node<T>.CreateThreeNode(parent.Value(), sibling.Value());
                    if (parent.LeftChild() == hole)
                    {
                        threeNode.SetLeftChild(hole.Child());
                        threeNode.SetMiddleChild(sibling.LeftChild());
                        threeNode.SetRightChild(sibling.RightChild());
                    }
                    else
                    {
                        threeNode.SetLeftChild(sibling.LeftChild());
                        threeNode.SetMiddleChild(sibling.RightChild());
                        threeNode.SetRightChild(hole.Child());
                    }

                    if (parent.Parent() == null)
                    {
                        UnlinkNode(hole);
                        root = threeNode;
                        hole = null;
                    }
                    else
                    {
                        hole.SetChild(threeNode);
                        parent.Parent().ReplaceChild(parent, hole);
                    }
                    UnlinkNode(parent);
                    UnlinkNode(sibling);

                }
                // Case 2. The hole has a 2-node as parent and 3-node as sibling.
                else if (hole.Parent().IsTwoNode() && hole.Sibling().IsThreeNode())
                {
                    //System.out.println("Case 2 ");
                    Node<T> parent = hole.Parent();
                    Node<T> sibling = hole.Sibling();

                    if (parent.LeftChild() == hole)
                    {
                        Node<T> leftChild = Node<T>.CreateTwoNode(parent.Value());
                        Node<T> rightChild = Node<T>.CreateTwoNode(sibling.RightValue());
                        parent.SetValue(sibling.LeftValue());
                        parent.ReplaceChild(hole, leftChild);
                        parent.ReplaceChild(sibling, rightChild);
                        leftChild.SetLeftChild(hole.Child());
                        leftChild.SetRightChild(sibling.LeftChild());
                        rightChild.SetLeftChild(sibling.MiddleChild());
                        rightChild.SetRightChild(sibling.RightChild());
                    }
                    else
                    {
                        Node<T> leftChild = Node<T>.CreateTwoNode(sibling.LeftValue());
                        Node<T> rightChild = Node<T>.CreateTwoNode(parent.Value());
                        parent.SetValue(sibling.RightValue());
                        parent.ReplaceChild(sibling, leftChild);
                        parent.ReplaceChild(hole, rightChild);
                        leftChild.SetLeftChild(sibling.LeftChild());
                        leftChild.SetRightChild(sibling.MiddleChild());
                        rightChild.SetLeftChild(sibling.RightChild());
                        rightChild.SetRightChild(hole.Child());
                    }
                    UnlinkNode(hole);
                    UnlinkNode(sibling);
                    hole = null;
                }

                // Case 3. The hole has a 3-node as parent and 2-node as sibling.
                else if (hole.Parent().IsThreeNode())
                {
                    Node<T> parent = hole.Parent();

                    // subcase (a), hole is in the middle
                    if (parent.MiddleChild() == hole && parent.LeftChild().IsTwoNode())
                    {
                        //System.out.println("Case 3 (a) hole in the middle");
                        Node<T> leftChild = parent.LeftChild();
                        Node<T> newParent = Node<T>.CreateTwoNode(parent.RightValue());
                        Node<T> newLeftChild = Node<T>.CreateThreeNode(leftChild.Value(), parent.LeftValue());
                        newParent.SetLeftChild(newLeftChild);
                        newParent.SetRightChild(parent.RightChild());
                        if (parent != root)
                        {
                            parent.Parent().ReplaceChild(parent, newParent);
                        }
                        else
                        {
                            root = newParent;
                        }

                        newLeftChild.SetLeftChild(leftChild.LeftChild());
                        newLeftChild.SetMiddleChild(leftChild.RightChild());
                        newLeftChild.SetRightChild(hole.Child());

                        UnlinkNode(parent);
                        UnlinkNode(leftChild);
                        UnlinkNode(hole);
                        hole = null;
                    }
                    // subcase (b), hole is in the middle
                    else if (parent.MiddleChild() == hole && parent.RightChild().IsTwoNode())
                    {
                        //System.out.println("Case 3(b) hole in the middle");
                        Node<T> rightChild = parent.RightChild();
                        Node<T> newParent = Node<T>.CreateTwoNode(parent.LeftValue());
                        Node<T> newRightChild = Node<T>.CreateThreeNode(parent.RightValue(), rightChild.Value());
                        newParent.SetLeftChild(parent.LeftChild());
                        newParent.SetRightChild(newRightChild);
                        if (parent != root)
                        {
                            parent.Parent().ReplaceChild(parent, newParent);
                        }
                        else
                        {
                            root = newParent;
                        }
                        newRightChild.SetLeftChild(hole.Child());
                        newRightChild.SetMiddleChild(rightChild.LeftChild());
                        newRightChild.SetRightChild(rightChild.RightChild());
                        UnlinkNode(parent);
                        UnlinkNode(rightChild);
                        UnlinkNode(hole);
                        hole = null;
                    }
                    else if (parent.MiddleChild().IsTwoNode())
                    {
                        Node<T> middleChild = parent.MiddleChild();

                        // subcase (a). hole is the left child.
                        if (parent.LeftChild() == hole)
                        {
                            //System.out.println("Case 3 (a) hole is left child");
                            Node<T> newParent = Node<T>.CreateTwoNode(parent.RightValue());
                            Node<T> leftChild = Node<T>.CreateThreeNode(parent.LeftValue(), middleChild.Value());
                            newParent.SetLeftChild(leftChild);
                            newParent.SetRightChild(parent.RightChild());
                            if (parent != root)
                            {
                                parent.Parent().ReplaceChild(parent, newParent);
                            }
                            else
                            {
                                root = newParent;
                            }

                            leftChild.SetLeftChild(hole.Child());
                            leftChild.SetMiddleChild(middleChild.LeftChild());
                            leftChild.SetRightChild(middleChild.RightChild());

                            UnlinkNode(parent);
                            UnlinkNode(hole);
                            UnlinkNode(middleChild);
                            hole = null;
                        }
                        // subcase (a). hole is the right child.
                        else if (parent.RightChild() == hole)
                        {
                            //System.out.println("Case 3 (a) hole is right child");
                            Node<T> newParent = Node<T>.CreateTwoNode(parent.LeftValue());
                            Node<T> rightChild = Node<T>.CreateThreeNode(middleChild.Value(), parent.RightValue());
                            newParent.SetRightChild(rightChild);
                            newParent.SetLeftChild(parent.LeftChild());
                            if (parent != root)
                            {
                                parent.Parent().ReplaceChild(parent, newParent);
                            }
                            else
                            {
                                root = newParent;
                            }

                            rightChild.SetLeftChild(middleChild.LeftChild());
                            rightChild.SetMiddleChild(middleChild.RightChild());
                            rightChild.SetRightChild(hole.Child());

                            UnlinkNode(parent);
                            UnlinkNode(hole);
                            UnlinkNode(middleChild);
                            hole = null;
                        }
                    }

                    // Case 4. The hole has a 3-node as parent and 3-node as sibling.

                    else if (parent.MiddleChild().IsThreeNode())
                    {
                        Node<T> middleChild = parent.MiddleChild();
                        // subcase (a) hole is the left child
                        if (hole == parent.LeftChild())
                        {
                            //System.out.println("Case 4 (a) hole is left child");
                            Node<T> newLeftChild = Node<T>.CreateTwoNode(parent.LeftValue());
                            Node<T> newMiddleChild = Node<T>.CreateTwoNode(middleChild.RightValue());
                            parent.SetLeftValue(middleChild.LeftValue());
                            parent.SetLeftChild(newLeftChild);
                            parent.SetMiddleChild(newMiddleChild);
                            newLeftChild.SetLeftChild(hole.Child());
                            newLeftChild.SetRightChild(middleChild.LeftChild());
                            newMiddleChild.SetLeftChild(middleChild.MiddleChild());
                            newMiddleChild.SetRightChild(middleChild.RightChild());

                            UnlinkNode(hole);
                            UnlinkNode(middleChild);
                            hole = null;
                        }
                        // subcase (b) hole is the right child
                        else if (hole == parent.RightChild())
                        {
                            // System.out.println("Case 4 (b) hole is right child");
                            Node<T> newMiddleChild = Node<T>.CreateTwoNode(middleChild.LeftValue());
                            Node<T> newRightChild = Node<T>.CreateTwoNode(parent.RightValue());
                            parent.SetRightValue(middleChild.RightValue());
                            parent.SetMiddleChild(newMiddleChild);
                            parent.SetRightChild(newRightChild);
                            newMiddleChild.SetLeftChild(middleChild.LeftChild());
                            newMiddleChild.SetRightChild(middleChild.MiddleChild());
                            // newMiddleChild.setParent(middleChild.MiddleChild());
                            newRightChild.SetLeftChild(middleChild.RightChild());
                            newRightChild.SetRightChild(hole.Child());

                            UnlinkNode(hole);
                            UnlinkNode(middleChild);
                            hole = null;

                        }
                        else if (hole == parent.MiddleChild() && parent.LeftChild().IsThreeNode())
                        {
                            // System.out.println("Case 4 (a) hole is middle child, left is 3-node");
                            Node<T> leftChild = parent.LeftChild();
                            Node<T> newLeftChild = Node<T>.CreateTwoNode(leftChild.LeftValue());
                            Node<T> newMiddleChild = Node<T>.CreateTwoNode(parent.LeftValue());
                            parent.SetLeftValue(leftChild.RightValue());
                            parent.SetLeftChild(newLeftChild);
                            parent.SetMiddleChild(newMiddleChild);
                            newLeftChild.SetLeftChild(leftChild.LeftChild());
                            newLeftChild.SetRightChild(leftChild.MiddleChild());
                            newMiddleChild.SetLeftChild(leftChild.RightChild());
                            newMiddleChild.SetRightChild(hole.Child());

                            UnlinkNode(hole);
                            UnlinkNode(leftChild);
                            hole = null;
                        }
                        else
                        {
                            System.Diagnostics.Debug.Assert((hole == parent.MiddleChild() && parent.RightChild().IsThreeNode()));
                            // System.out.println("Case 4 (b) hole is middle child, right is 3-node");
                            Node<T> rightChild = parent.RightChild();
                            Node<T> newRightChild = Node<T>.CreateTwoNode(rightChild.RightValue());
                            Node<T> newMiddleChild = Node<T>.CreateTwoNode(parent.RightValue());
                            parent.SetRightValue(rightChild.LeftValue());
                            parent.SetMiddleChild(newMiddleChild);
                            parent.SetRightChild(newRightChild);
                            newRightChild.SetRightChild(rightChild.RightChild());
                            newRightChild.SetLeftChild(rightChild.MiddleChild());
                            newMiddleChild.SetRightChild(rightChild.LeftChild());
                            newMiddleChild.SetLeftChild(hole.Child());

                            UnlinkNode(hole);
                            UnlinkNode(rightChild);
                            hole = null;
                        }
                    }

                }
            }

            size--;
            return true;
        }

        private void UnlinkNode(Node<T> node)
        {
            node.RemoveChildren();
            node.SetParent(null);
        }

        private Node<T> Successor(Node<T> node, T value)
        {
            if (node == null)
                return null;

            if (!node.IsTerminal())
            {
                Node<T> p;
                if (node.IsThreeNode() && node.LeftValue().Equals(value))
                {
                    p = node.MiddleChild();
                }
                else
                {
                    p = node.RightChild();
                }
                while (p.LeftChild() != null)
                {
                    p = p.LeftChild();
                }
                return p;
            }
            else
            {
                Node<T> p = node.Parent();
                if (p == null) return null;

                Node<T> ch = node;
                while (p != null && ch == p.RightChild())
                {
                    ch = p;
                    p = p.Parent();
                }
                return p != null ? p : null;
            }
        }

        private Node<T> Predecessor(Node<T> node, T value)
        {
            if (node == null)
                return null;

            Node<T> p;
            if (!node.IsTerminal())
            {
                if (node.IsThreeNode() && node.RightValue().Equals(value))
                {
                    p = node.MiddleChild();
                }
                else
                {
                    p = node.LeftChild();
                }

                while (p.RightChild() != null)
                {
                    p = p.RightChild();
                }
                return p;
            }
            else
            {
                throw new Exception("Implement predecessor parent is not terminal node");
            }

        }

        private Node<T> SplitNode(Node<T> threeNode, T value)
        {
            T min;
            T max;
            T middle;
            if (value.CompareTo(threeNode.LeftValue()) < 0)
            {
                min = value;
                middle = threeNode.LeftValue();
                max = threeNode.RightValue();
            }
            else if (value.CompareTo(threeNode.RightValue()) < 0)
            {
                min = threeNode.LeftValue();
                middle = value;
                max = threeNode.RightValue();
            }
            else
            {
                min = threeNode.LeftValue();
                max = value;
                middle = threeNode.RightValue();
            }

            Node<T> parent = Node<T>.CreateTwoNode(middle);
            parent.SetLeftChild(Node<T>.CreateTwoNode(min));
            parent.SetRightChild(Node<T>.CreateTwoNode(max));
            return parent;
        }

        #region traval
        /**
         * Preorder search.
         * Visit the node.
         * Visit the left subtree
         * Visit the middle subtree
    
         */
        public void PreOrder(Node<T> node, Action<Node<T>> func)
        {
            //if (node.IsThreeNode())
            //{
            //    func(node.LeftChild());
            //    func(node.MiddleChild());
            //    func(node.RightChild());
            //}

            //if (node.IsTerminal())
            //{
            //    return;
            //}
            func(node);
            if (node != null)
            {
                PreOrder(node.LeftChild(), func);
                if (node.IsThreeNode())
                {
                    PreOrder(node.MiddleChild(), func);
                }
                PreOrder(node.RightChild(), func);
            }
        }

        public void InOrderSearch(Node<T> node, Action<T, string> func)
        {
            if (node == null)
            {
                return;
            }

            InOrderSearch(node.LeftChild(), func);

            if (node.IsThreeNode())
            {
                Node<T> threeNode = node;

                func(threeNode.LeftValue(), "(");

                InOrderSearch(threeNode.MiddleChild(), func);

                func(threeNode.RightValue(), ")");
            }
            else
            {
                func(node.Value(), string.Empty);
            }

            InOrderSearch(node.RightChild(), func);
        }


        // Set operations.

        public T First()
        {
            Node<T> node = root;
            while (node.LeftChild() != null)
            {
                node = node.LeftChild();
            }
            return node.IsThreeNode() ? node.LeftValue() : node.Value();
        }

        public T Last()
        {
            Node<T> node = root;
            while (node.RightChild() != null)
            {
                node = node.RightChild();
            }
            return node.IsThreeNode() ? node.RightValue() : node.Value();
        }

        #endregion

        public int Count
        {
            get
            {
                return size;
            }
        }


        public void Clear()
        {
            root = null;
        }

        public bool RemoveAll(ICollection<T> c)
        {
            bool removed = false;
            foreach (T o in c)
            {
                removed |= Remove(o);
            }
            return removed;
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            throw new NotImplementedException();
        }

        public bool IsReadOnly
        {
            get
            {
                return false;
            }
        }

        public override string ToString()
        {
            if (size == 0)
            {
                return string.Empty;
            }

            StringBuilder sb = new StringBuilder();

            IEnumerable<Node<T>> list = GetList();

            foreach (Node<T> item in list.OrderBy(e => e.GetDepth()))
            {
                sb.AppendLine(item.ToString());
            }

            sb.Remove(sb.Length - 1, 1);
            
            return sb.ToString();
        }

        #region IEnumerable Members

        private IEnumerable<Node<T>> GetList()
        {
            List<Node<T>> list = new List<Node<T>>();

            PreOrder(root,
                (t) =>
                {
                    if (t != null)
                    {
                        list.Add(t);
                    }
                });

            return list;
        }

        public IEnumerator<T> GetEnumerator()
        {
            IEnumerable<Node<T>> list = GetList();

            return list.AsParallel().Select(e => e.Value()).GetEnumerator();
        }

        #endregion

        #region IEnumerable Members


        IEnumerator IEnumerable.GetEnumerator()
        {
            throw new NotImplementedException();
        }


        #endregion


    }

}
